/**
 * https://leetcode.cn/problems/count-ways-to-build-good-strings/submissions/562932840/
 * 2466. 统计构造好字符串的方案数
 * medium 陈贝纯 2024.09.09
 * 经典线性
 */

class Solution {
public:
    typedef long long ll;
    const ll mod=1e9+7;
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<ll>dp(high+1);
        dp[0]=1;
        for(int i=1;i<=high;++i){
            if(i>=zero)
                dp[i]=((dp[i]%mod)+(dp[i-zero]%mod))%mod;
            if(i>=one)
            dp[i]=((dp[i]%mod)+(dp[i-one]%mod))%mod;
        }
        ll sum=0;
        for(int i=low;i<=high;++i)
            sum=((sum%mod)+(dp[i]%mod))%mod;
            return sum;
    }
};